template <typename T>
class UnionFindSet
{
public:
    UnionFindSet()
    {
    }

    template <typename TContainer>
    UnionFindSet(const TContainer &container)
    {
        auto begin = container.begin();
        auto end = container.end();
        while (begin != end)
        {
            m[*begin] = *begin;
            ++begin;
        }
    }

    void insert(const T &value)
    {
        if (!m.count(value))
        {
            m[value] = value;
        }
    }

    bool exist(const T &value)
    {
        return m.count(value);
    }

    T find(const T &value)
    {
        if (m[value] == value)
        {
            return value;
        }
        return m[value] = find(m[value]);
    }

    void join(const T &value1, const T &value2)
    {
        if (find(value1) != find(value2))
        {
            m[find(value1)] = find(value2);
        }
    }

private:
    std::unordered_map<T, T> m;
};

class Solution
{
public:
    // 总体来说这是个暴力解法
    int magnificentSets(int n, vector<vector<int>> &edges)
    {
        vector<vector<int>> adjTable(n + 1);
        vector<int> nums(n);
        iota(nums.begin(), nums.end(), 1);
        UnionFindSet<int> ufs(nums);
        for (auto &edge : edges)
        {
            adjTable[edge[0]].push_back(edge[1]);
            adjTable[edge[1]].push_back(edge[0]);
            ufs.join(edge[0], edge[1]);
        }
        unordered_map<int, unordered_set<int>> connectedParts;
        for (int i = 1; i <= n; ++i)
        {
            connectedParts[ufs.find(i)].insert(i);
        }

        int allMaxGroupCount = 0;
        for (auto &[_, connectedPart] : connectedParts) // 每个连通区域分别处理
        {
            int partMaxGroupCount = 0;
            for (int startNode : connectedPart) // 从每个节点出发BFS，每一层的所有邻接接点要么放在新组，要么在上一层
            {
                int groupId = 1;
                unordered_map<int, int> groupMap;
                groupMap[startNode] = groupId;
                queue<int> q;
                q.push(startNode);
                while (!q.empty())
                {
                    int groupSize = q.size();
                    for (int i = 0; i < groupSize; ++i)
                    {
                        int node = q.front();
                        q.pop();
                        for (int nearNode : adjTable[node])
                        {
                            if (groupMap.count(nearNode))
                            {
                                if (abs(groupMap[nearNode] - groupId) != 1)
                                {
                                    // 目测，不能分组等价于存在奇数长度的环，所以一种情况不能分组就全都不能分组，有待考证
                                    return -1;
                                }
                            }
                            else
                            {
                                groupMap[nearNode] = groupId + 1;
                                q.push(nearNode);
                            }
                        }
                    }
                    ++groupId;
                }
                partMaxGroupCount = max(partMaxGroupCount, groupId - 1);
            }
            allMaxGroupCount += partMaxGroupCount;
        }
        return allMaxGroupCount;
    }
};